/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */

#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <math.h>

#define ROOT_PID 0
#define META_DATA_PID 0

#define MAX_PTRS       ceil( (PageFile::PAGE_SIZE+sizeof(int))/(sizeof(RecordId)+sizeof(int)) )
#define MAX_KEYS       LEAF_MAX_POINTERS-1 


#define LEAF_MIN_PTRS       ceil( (MAX_PTRS+1)/2 )
#define LEAF_MIN_KEYS       ceil( (MAX_PTRS-1)/2 )

#define NONLEAF_MIN_PTRS    ceil( MAX_PTRS/2 )
#define NONLEAF_MIN_KEYS    ceil( MAX_PTRS/2 ) -1

#define ROOT_MIN_PTRS       2
#define ROOT_MIN_KEYS       1


/*
 leaf buffer
 -----------------------------------------------------------
 | | | ... | | | root pid | treeHeight | #keys | NextPointer
 -----------------------------------------------------------
 */

//#define TOTAL_ENTRIES getKeyCount()
#define AVAILABLE_SPACE PageFile::PAGE_SIZE-sizeof(PageId)-sizeof(int)-sizeof(PageId)-sizeof(int)

// LEAF
#define L_ENTRY_SIZE sizeof(RecordId)+sizeof(int)
//#define L_TAKEN_SPACE getKeyCount()*L_ENTRY_SIZE

// NONLEAF
#define NL_ENTRY_SIZE sizeof(PageId)+sizeof(int)
//#define NL_TAKEN_SPACE getKeyCount()*NL_ENTRY_SIZE

// OFFSETS
#define OFFSET_ROOTPID AVAILABLE_SPACE
#define OFFSET_TREEHEIGHT OFFSET_ROOTPID + sizeof(PageId)
#define OFFSET_KEY      OFFSET_TREEHEIGHT + sizeof(int)
#define OFFSET_NEXTPTR  OFFSET_KEY + sizeof(int)

using namespace std;

// ********* Helper functions *********//
/*
 PageId getRootPid(const char* page) 
 {
 // The first four bytes of a 
 PageId pid;
 memcpy(&pid, page, sizeof(PageId));
 return pid;
 }
 
 int getRootPageHeight(const char* page)
 {
 int height;
 memcpy(&height, page+sizeof(PageId), sizeof(int));
 return height;
 }
 */
//*************************************//


/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

BTreeIndex::~BTreeIndex()
{
    // get a buffer to the first root page
    char rootPage[PageFile::PAGE_SIZE];
    pf.read(META_DATA_PID, rootPage);
    
    // write the first 8 bytes of the buffer
    // to store rootPid and treeHeight
    memcpy(rootPage+OFFSET_ROOTPID, &rootPid, sizeof(PageId));
    memcpy(rootPage+OFFSET_TREEHEIGHT, &treeHeight, sizeof(int));
    
    // store the buffer to the disk
    pf.write(META_DATA_PID,rootPage);
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    RC rc;
    char rootPage[PageFile::PAGE_SIZE];
    
    // open the page file
    // If unable to open, return error
    if ((rc = pf.open(indexname, mode)) < 0) return rc;
    
    // if the file was just created or is empty
    // set the rootPid and height variables to -1
    if (pf.endPid() == 0)
    {
        rootPid = -1;
        treeHeight = -1;
        return 0;
    }
    
    // Index file was already created,
    // Try to read from the root page (pid=0),
    // return error if can not read
    if ((rc = pf.read(ROOT_PID, rootPage)) < 0) {
        // an error occurred during page read
        rootPid = -1;
        treeHeight = -1;
        return rc;
    }
    
    // Restore rootPid and treeHeight from the root page of
    // the index file
    memcpy(&rootPid, rootPage+OFFSET_ROOTPID, sizeof(PageId));
    memcpy(&treeHeight, rootPage+OFFSET_TREEHEIGHT, sizeof(int));
    
    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    rootPid = 0;
    treeHeight = 0;
    
    return pf.close();
}


/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    /*
     
     If the bucket is not full, add the record.
     Otherwise, split the bucket.
     Allocate new leaf and move half the bucket's elements to the new bucket.
     Insert the new leaf's smallest key and address into the parent.
     If the parent is full, split it too.
     Add the middle key to the parent node.
     Repeat until a parent is found that need not split.
     If the root splits, create a new root which has one key and two pointers.
     
     */
    
    RC rc;
    
    // if empty tree
    if (treeHeight == -1) {
        BTLeafNode l_node;
        
        // insert the (key,rid) pair into the node
        l_node.insert(key, rid);
        
        // commit the new node to pagefile
        rootPid = pf.endPid();
        rc = l_node.write(rootPid, pf);
        
        // set tree height
        treeHeight = 0;
    }
    // else insert into tree
    else {
        PageId sibpid;
        int sibkey;
        rc = insertEntry(key,rid,rootPid,treeHeight, sibpid, sibkey);
    }
    
    return rc;
}

/* insertEntry - recursive helper function to insert an entry into a tree
 * [IN] key - key to insert
 * [IN] rid - rid to insert
 * [IN] curPID - pid of the current node being processed
 * [IN] curHeight - the height in the tree of the node being processed
 * [OUT] sibPID - used to pass sibling node's pid
 * [OUT] sibKey - used to pass middle key to be pushed up
 */

RC BTreeIndex::insertEntry(int key, const RecordId& rid, PageId curPID, int curHeight, PageId& sibPID, int& sibKey) 
{
    // Base Case - at the leaf node
    if (curHeight == treeHeight) {
        RC rc = 0;
        
        // Pull the data into a leaf node object
        BTLeafNode l_node;
        l_node.read(curPID, pf);
        
        // If bucket is not full, add the record
        // Else split the bucket
        if ((rc = l_node.insert(key,rid)) == 0) {
            l_node.write(curPID,pf);
            return 0;
        }
        else {
            // Construct new sibling leaf
            BTLeafNode sib_node;
            
            // Move half the bucket's elements to new bucket
            // and insert record
            // Also, updates [OUT] sibKey
            l_node.insertAndSplit(key, rid, sib_node, sibKey);
            
            // commit changes to pageFile, updates [OUT] sibPID
            sibPID = pf.endPid();            
            sib_node.write(sibPID, pf);
            
            // Set current leaf's next pointer to sibling leaf
            l_node.setNextNodePtr(sibPID);
            l_node.write(curPID, pf);
            
            // Add new root if overflow at the current root
            if (curHeight == 0) {
                // construct a new root node and initialize it
                BTNonLeafNode root;
                rc = root.initializeRoot(curPID,sibKey,sibPID);
                
                // commit changes to page file
                PageId r_pid = pf.endPid();
                root.write(r_pid,pf);
                
                return rc;
            }
            
            
            // Add the middle key to the parent node recursively
            // in the previous record, insert needed indicated
            // by return value
            return RC_NODE_FULL;
        }
        
    }
    else {  // NON-LEAF NODE
        RC rc = 0;
        
        // Pull data into nonleaf node
        BTNonLeafNode nl_node;
        nl_node.read(curPID, pf);
        
        // Find the pointer to follow
        PageId next_pid;
        nl_node.locateChildPtr(key, next_pid);
        
        int midKey;
        PageId retPID;
        // Attempt to insert the entry into the next level
        if ((rc = insertEntry(key, rid, next_pid, curHeight+1, retPID, midKey  )) < 0) {
            
            // insertEntry returned after recursive call
            // with new midkey to be pushed up and inserted
            
            // If we can insert with no overflow, do so
            if ((rc = nl_node.insert(midKey, retPID)) == 0) {
                rc = nl_node.write(curPID,pf);
                return rc;
            }
            // else, overflow, 
            else {
                
                // Insert and split needed for non-leaf node
                BTNonLeafNode new_sib_node;
                int new_midKey;
                if ((rc = nl_node.insertAndSplit(midKey, retPID, new_sib_node, new_midKey)) < 0) return -1;
                
                // commit new sibling to pageFile
                PageId new_sibPID = pf.endPid();
                new_sib_node.write(new_sibPID, pf);
                
                // commit updated current nonleaf node to Pagefile
                nl_node.write(curPID,pf);
                
                // If this is the root node, make new root
                if (curHeight == 0) {
                    // construct a new root node and initialize it
                    BTNonLeafNode root;
                    rc = root.initializeRoot(curPID,new_midKey,new_sibPID);
                    
                    // commit changes to page file
                    PageId r_pid = pf.endPid();
                    root.write(r_pid,pf);
                    
                    // Final return because we're at top of the
                    // recursive stack
                    return rc;
                }
                
                // update the return values
                sibPID = new_sibPID;
                sibKey = new_midKey;
                
                // We have set the new values to be pushed to the
                // next level, and will insert in the recursive record
                // following this return
                return RC_NODE_FULL;
            }
        }
        else {
            // insertEntry returned after recursive call
            // with no overflows
            return rc;
        }
    }
    return -1;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    RC rc;
    int curHeight = 0;
    
    // Temporary Nodes + variables for searching
    BTNonLeafNode nl_node;
    BTLeafNode l_node;
    PageId nextChildPid = rootPid;
    
    while (curHeight < treeHeight) {        
        // Update the nl_node to represent the new node after following pointer
        if ((rc = nl_node.read(nextChildPid,pf)) < 0) return rc;
        
        // Choose the correct pointer in the node to follow -> NextChildPid
        if ((rc = nl_node.locateChildPtr(searchKey, nextChildPid)) < 0) return rc;
        
        curHeight++;
    }
    
    // Got out of the while loop so we are at a leaf node
    // Read page into l_node's buffer. Find the search key
    // to get the eid. Then update the IndexCursor.
    int eid = 0;
    if ((rc = l_node.read(nextChildPid,pf)) < 0) return rc;
    if ((rc = l_node.locate(searchKey, eid)) < 0) return rc;
    cursor.eid = eid;
    cursor.pid = nextChildPid;
    
    return rc;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    RC rc;
	BTLeafNode l_node;
	//cursor has pid and eid
	//check to make sure that the pid and eid are valid
	if (cursor.pid < 0 || cursor.eid < 0){
		return RC_INVALID_CURSOR;
	}
	//read the entry
	if ((rc = l_node.read(cursor.pid, pf)) < 0) return rc;
	if ((rc = l_node.readEntry(cursor.eid, key, rid)) < 0) return rc;
	
	//move the cursor to next entry
	if ((cursor.eid + 1) >= l_node.getKeyCount()){ //make sure to move eid if we are past the last eid
		cursor.eid = 0;
		cursor.pid = l_node.getNextNodePtr();
	} //else pid stays the same but cursor.eid is incremented
	else{
		cursor.eid++;
	}
    return 0;
}
